package RedBook.red7_23;

import java.util.Scanner;


//小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？
//
//
//
//        输入描述
//        第一行输入一个正整数t，代表询问次数。
//
//        对于每次询问，输入两行：
//
//        第一行输入两个正整数n和x。代表数组的大小，以及小红可以修改成的元素。
//
//        第二行输入n个正整数a_i，代表小红拿到的数组。
//
//        1 ≤ t ≤ 100000
//
//        1 ≤ n ≤ 200000
//
//        -10^9 ≤ x ,a_i ≤ 10^9
//
//        每组所有询问的n的和不超过200000。
//
//        输出描述
//        输出t行，每行输出一个整数，代表连续子数组的最大和。




public class  Test3 {


//    动态规划。
//
//    假设修改点为i，不难想到，最后的答案应该是  [0,i-1]中，以i-1结尾的最大和子数组，
//    加上 [i+1,n-1]中，以i+1结尾的最大和子数组，因此我们可以预处理出 正向最大子数组 和 逆向最大子数组，枚举修改点即可。
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int t = sc.nextInt();
//        while (t-->0) {
//            int n = sc.nextInt();
//            int x = sc.nextInt();
//            int[] a = new int[n];
//            for (int i = 0; i < n; i++) {
//                a[i] = sc.nextInt();
//            }
        int n=5;
        int x = 10;
        int[] a = {5,-1,-5,-3,2};
            int[] dp1 = new int[n];
            dp1[0] = a[0];
            int res = Integer.MIN_VALUE;
            for (int i = 1; i < n; i++) {
                dp1[i] = Math.max(dp1[i-1] + a[i], a[i]);
                res = Math.max(res, dp1[i]);
            }

            System.out.println("==================================================");
            for (int cu:dp1) {
                System.out.println(cu);
            }
            System.out.println("==================================================");


            int[] dp2 = new int[n];
            dp2[n - 1] = a[n - 1];

            for (int i = n - 2; i>= 0 ; i--) {
                dp2[i] = Math.max(dp2[i+1] + a[i], a[i]);
            }


            System.out.println("------------------------------------------");
            for (int cu:dp2) {
                System.out.println(cu);
            }
            System.out.println("------------------------------------------");


            for (int i = 0 ; i < n ; i++) {

                res = Math.max(res, (i> 0 && dp1[i-1] > 0 ? dp1[i-1] : 0) + (i < n - 1 && dp2[i+1] > 0 ? dp2[i+1]: 0) + x);
            }

            System.out.println(res);
        }
    }

//
//    public static void main(String[] args) {
////        Scanner scanner = new Scanner(System.in);
////        int t = scanner.nextInt();
////        for (int i = 0; i <t ; i++) {
////            perNums();
////        }
//        int[] arr={-1,-2,3};
//        System.out.println(getMax(arr, 10));
//    }
//
//    public static void  perNums(){
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int x = scanner.nextInt();
//        int[] nums = new int[n];
//        for (int i = 0; i < n; i++) {
//            nums[i]=scanner.nextInt();
//        }
//        System.out.println(getMax(nums, x));
//    }
//
//    public  static int getMax(int[] nums,int x){
//        int length = nums.length;
//        int maxSum=0;
//        int currentSum=0;
//        int maxEndingHere=0;
//        int maxSofar=0;
//        for (int i = 0; i < length; i++) {
//            currentSum+=nums[i];
//            maxEndingHere=Math.max(nums[i],maxEndingHere+nums[i]);
//            maxSofar=Math.max(maxSofar,maxEndingHere);
//            maxSum=Math.max(maxSum,currentSum);
//        }
//
//        return  Math.max(maxSum,maxSofar+x);
//
//    }





// class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int t = scanner.nextInt(); // 询问次数
//        for (int i = 0; i < t; i++) {
//            int n = scanner.nextInt(); // 数组的大小
//            int x = scanner.nextInt(); // 可以修改的元素
//            int[] array = new int[n];
//            for (int j = 0; j < n; j++) {
//                array[j] = scanner.nextInt();
//            }
//            int maxSum = getMaxSum(array, x);
//            System.out.println(maxSum);
//        }
//    }
//
//
//    public static int getMaxSum(int[] array, int x) {
//        int maxSum = 0;
//        int curSum = 0;
//        for (int i = 0; i < array.length; i++) {
//            curSum += array[i];
//            if (curSum < 0) {
//                curSum = 0;
//            }
//            maxSum = Math.max(maxSum, curSum);
//        }
//        if (x < 0 && maxSum == 0) {
//            return x;
//        } else {
//            return maxSum + x;
//        }
//    }
//}


//class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int t = scanner.nextInt(); // 询问次数
//        for (int i = 0; i < t; i++) {
//            int n = scanner.nextInt(); // 数组的大小
//            int x = scanner.nextInt(); // 可以修改成的元素
//
//            // 输入数组
//            int[] arr = new int[n];
//            for (int j = 0; j < n; j++) {
//                arr[j] = scanner.nextInt();
//            }
//
//            // 解决当前询问
//            int result = maxSubarraySumAfterOneModification(arr, x);
//            System.out.println(result);
//        }
//    }
//
//    // 计算最大连续子数组和
//    public static int maxSubarraySumAfterOneModification(int[] arr, int x) {
//        int n = arr.length;
//        int maxEndingHere = arr[0]; // 当前连续子数组的最大和（包含最后一个元素）
//        int maxSoFar = arr[0]; // 目前遍历过的连续子数组的最大和
//
//        // 计算不修改元素时的最大连续子数组和
//        for (int i = 1; i < n; i++) {
//            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
//            System.out.println(maxEndingHere);
//            maxSoFar = Math.max(maxSoFar, maxEndingHere);
//        }
//
//        // 计算允许修改一个元素时的最大连续子数组和
//        int maxAfterModification = Integer.MIN_VALUE;
//        maxEndingHere = 0;
//        for (int i = 0; i < n; i++) {
//            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
//            System.out.println(maxEndingHere);
//            maxAfterModification = Math.max(maxAfterModification, maxEndingHere);
//        }
//
//
//
//        // 检查是否有必要修改元素
//        if (maxSoFar >= maxAfterModification) {
//            return maxSoFar;
//        } else {
//            // 修改一个元素后的最大连续子数组和
//            return maxAfterModification + x;
//        }
//    }
//}
